/**
 * @file   priorityqueue.h
 * @author WinterMelonCDY <wintermeloncdy@wintermeloncdy-VirtualBox>
 * @date   Wed Dec 22 17:33:42 2021
 * 
 * @brief  
 * 
 * 
 */
#include <vector>
#include <map>
#include <iostream>
using namespace std;



template <typename Unique, typename Comparable>
struct DataBase
{
    Unique key;
    Comparable data;
};

template<typename Unique,typename Comparable>
DataBase<Unique,Comparable> generate(Unique key, Comparable data)
{
    DataBase<Unique,Comparable> A;
    A.key=key;
    A.data=data;
    return A;
}

template <typename Unique, typename Comparable>
class PriorityQueue
{

public:
    vector<DataBase<Unique, Comparable>> array;
    int len;
    map<Unique, int> keymap;

    void insert(const DataBase<Unique, Comparable> &_x)
    {
        array.resize(array.size()+1);
        array[0] = _x;
        upshift(array.size()-1);

    }; // Insert a new data

    void insert(DataBase<Unique, Comparable> &&_x)
    {
        array.resize(array.size()+1);
        array[0] = _x;
        upshift(array.size()-1);
    }; // Insert a new data

    void deleteMin()
    {
        keymap.erase(array[1].key);
        array[0] = array[array.size() - 1];
        keymap[array[array.size() - 1].key] = 0;
        array.pop_back();
        downshift(1);

    }; // Delete the minimum data

    void pri()
    {
        cout<<"pri:";
        for(int i=1;i<array.size();i++)
        cout<<" "<<array[i].data;
        cout<<endl;
    }

    void downshift(int index)
    {
        if (array.size() < index * 2 + 1) // No children
        {
            array[index] = array[0];
            keymap[array[index].key] = index;
        }
        else if (array.size() == index * 2 + 1) // One child
        {
            if (array[0].data > array[index * 2].data)
            {
                array[index] = array[index * 2];
                keymap[array[index].key] = index;
                array[2 * index] = array[0];
                keymap[array[2 * index].key] = 2 * index;
            }
            else
            {
                array[index] = array[0];
                keymap[array[index].key] = index;
            }
        }
        else // Two children
        {

            if (array[2 * index].data > array[0].data && array[2 * index + 1].data > array[0].data) // when two children are both bigger
            {
                array[index] = array[0];
                keymap[array[index].key] = index;
            }
            else if (array[2 * index].data<array[2 * index+1].data) // when the left child is smaller
            {
                array[index] = array[index * 2];
                keymap[array[index].key] = index;
                downshift(2 * index);
            }
            else // when thr right child is smaller
            {
                array[index] = array[index * 2 + 1];
                keymap[array[index].key] = index;
                downshift(2 * index + 1);
            }
        }
    }

    void buildHeap(const vector<DataBase<Unique, Comparable>> &_input)
    {
        array.resize(1);
        for(int i=0;i<_input.size();i++)
        {

            insert(_input[i]);
        }
        
    };

    void remove(Unique k)
    {
        if (keymap.count(k) == 0)
        {
        }
        else
        {
            int index = keymap[k];
            int h = 1;
            int amo = 1;
            while (index / amo != 0)
            {
                h++;
                amo = amo * 2;
            }
            for (int i = 0; i < h - 1; i++)
            {
                array[index] = array[index / 2];
                keymap[array[index].key] = index;
                index = index / 2;
            }
            deleteMin();
        }

    }; // Search for key data "k",delete it if it can be found
    void modifyData(Unique k, Comparable d)
    {
        int index = keymap[k];
        Comparable tem=array[index].data+d;
        remove(k);
        insert(generate(k,tem));

    }; // Search for key data "k",add "d"
    void upshift(int index)
    {
        if (index == 1 || array[index / 2].data < array[0].data)
        {

            array[index] = array[0];
            keymap[array[index].key] = index;
        }
        else
        {
            array[index] = array[index / 2];
            keymap[array[index].key] = index;
            upshift(index / 2);
        }
    }
};
